Introduction

This is the most natural security definition for public-key encryption schemes, since the public key is available for anyone to see. Any realistic adversary would have access to it, and, since they know the encryption algorithm, they can use to encrypt any message they like. This is the reason why chosen-plaintext security is the minimal security guarantee which is expected of public-key encryption schemes.

The efficient adversary $\textit{Eve}$ is given the public key $k_e$ and can use it to encrypt $q$ messages of her choice $m_1, ..., m_q$ to obtain their corresponding ciphertexts $c_1, ..., c_q$. 

A public-key encryption scheme $(\textit{Gen}, \textit{Enc}, \textit{Dec})$ is *CPA-secure* if for any two messages $(\mu_0, \mu_1)$, public key $k_e$ generated by $\textit{Gen}$ and ciphertext $c \coloneqq \textit{Enc}(k_e, \cdot)$ which is the encryption of either $\mu_0$ or $\mu_1$, the probability that Eve can guess whether $c$ belongs to $\mu_0$ or $\mu_1$ is at most negligibly greater than $\frac{1}{2}$.

$$\Pr_{k_e \leftarrow \textit{Gen}(), b \leftarrow_R \{0,1\}}[\textit{Eve}(k_e, \textit{Enc}(k_e, \mu_b)) = \mu_b] \le \frac{1}{2} + \textit{negl}()$$
Copy

The adversary Eve is not explicitly given access to an encryption oracle because she has the public key, knows the encryption algorithm and can thus encrypt any messages she likes. She is also free to choose the messages $\mu_0, \mu_1$. The public-key encryption scheme is considered CPA-secure if no matter what Eve does, she cannot guess if a ciphertext $c$ is the encryption of $\mu_0$ or $\mu_1$ with significantly better probability than $\frac{1}{2}$.
Copy

As with private-key CPA-security, any public-key encryption scheme must use a nondeterministic function.

There is no CPA-secure public-key encryption scheme with a deterministic encryption function $\textit{Enc}$.
Copy

If the encryption algorithm were deterministic, then Eve would be able to simply pass and to it and compare with the resulting ciphertexts. Non-determinism protects against this by producing a different ciphertext every time that the same message is encrypted.